package Ep06_BinaryTree.BT28_0235;

import Ep06_BinaryTree.TreeNode;

/**
 * @author Jimmy Zhan WORKSTATION
 * @date 2023/7/8 18:42
 * 说明：二叉搜索树求公共祖先
 *      因为也是二叉树，所以也可以用236的方法，从底层向上遍历并传递结果
 *      但是二叉搜索树的特性可别忘了，左子树和右子树是存在大小关系的
 *
 * 思路：
 *     普通二叉树找祖先得后序遍历自下而上去搜索
 *     二叉搜索树就不一样了，可以由上而下去遍历，在每次遍历的时候对比其值来确定下一步往哪儿走
 *     题意中所有节点的值都是唯一的，且结果一定存在于树中
 *     1. 如果当前节点比p和q都大，那么要找的公共祖先就一定在左子树中
 *     2. 如果当前节点比p和q都小，那么要找的公共祖先就一定在右子树中
 *     3. 如果当前节点在p和q中间，说明当前就是公共祖先
 *
 *     eg: p=3, q=7 那么公共祖先就是6。
 *     虽然4也在3和7中间，但是在6的时候就return了，走不到4，因此没有问题
 */

public class Best {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root.val > p.val && root.val > q.val) {
            return lowestCommonAncestor(root.left, p, q);
        } else if (root.val < p.val && root.val < q.val) {
            return lowestCommonAncestor(root.right, p, q);
        }
        return root;
    }
}
